package 题;

import java.lang.classfile.components.ClassPrinter;
import java.sql.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test {
    //题一原地移除数组中所有元素val
    public int removeElement(int[] nums, int val) {
       int left=0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right]!=val){
                nums[left]=nums[right];
                left++;
            }
        }
        return left;
    }
    public int removeElement3(int[] nums, int val) {
        int k= 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]!=val){
                k++;
            }
        }
        return k;
    }
    //题二删除排序数组中的重复项
    public int removeDuplicates(int[] nums) {
        int left = 0;
        int right = left+1;
        while(right<nums.length){
            if(nums[left]==nums[right]){
                right++;
            }else{
                nums[left+1]=nums[right];
                left++;
            }
        }
        return left+1;
    }
    public static void main(String[] args) {
        Test test = new Test();
        int[] ret={1,2,3,1,5,4};
        int k=test.removeElement(ret,1);
        System.out.println(k);

    }
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] array=new int[n+m];
        int cur=0;
        int j=0;
        int i=0;
        while (i<=m&&j<=n){
            if (nums1[i]<=nums2[j]){
                array[cur]=nums1[i];
                i++;
                cur++;
            }else {
                array[cur]=nums2[j];
                j++;
                cur++;
            }
        }
        while (i<=m){
            array[cur]=nums1[i];
            i++;
            cur++;
        }
        while (j<=n){
            array[cur]=nums2[j];
            cur++;
            j++;
        }
        for (int k = 0; k < array.length; k++) {
            nums1[k]=array[k];
        }
    }
    //题五杨辉三角
    public List<List<Integer>> generate(int numRows) {
      List<List<Integer>> ret = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> ret2=new ArrayList<>();
            for (int j = 0; j <=i; j++) {
                if (j==0||j==i){
                    ret2.add(1);
                }else {
                    ret2.add(ret.get(i-1).get(j-1)+ret.get(i-1).get(j));
                }
            }
            ret.add(ret2);
        }
        return ret;
    }

      public class ListNode {
       int val;
       ListNode next;
       ListNode() {}
       ListNode(int val) { this.val = val; }
       ListNode(int val, ListNode next) { this.val = val; this.next = next; }
      }
    public ListNode removeElements(ListNode head, int val) {
        while (head != null && head.val == val) {
            head = head.next;
        }
        if (head == null) {
            return null;
        }
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }

        }
        return head;
    }
    public int removeElement2(int[] nums, int val) {
        if (nums==null){
            return 0;
        }
        int left=0;
        int right=nums.length-1;
        while (left>right){
            if (nums[left]!=val){
                left++;
            }else {
                nums[left]=nums[right];
                right--;
            }
        }
        return left;
    }
    public int removeDuplicates2(int[] nums) {
        if (nums==null){
            return 0;
        }
        int left=0;
        for (int right = left+1; right < nums.length; right++) {
            if (nums[right]!=nums[left]){
                nums[left+1]=nums[right];
                left++;
            }
        }
        return left+1;

    }
    public void merge2(int[] nums1, int m, int[] nums2, int n) {
        int[] array = new int[n+m];
        int i=0;
        int j=0;
        int cur=0;
        while (i<m&&j<n){
            if (nums1[i]<=nums2[j]){
                array[cur]=nums1[i];
                i++;
                cur++;
            }else {
                array[cur]=nums2[j];
                j++;
                cur++;
            }
        }
        while (i<m){
            array[cur]=nums1[i];
            i++;
            cur++;
        }
        while (j<n){
            array[cur]=nums2[j];
            j++;
            cur++;
        }
        for (int k = 0; k < array.length; k++) {
            nums1[k]=array[k];
        }
    }
    public List<List<Integer>> generate10(int numRows) {
    List<List<Integer>> list = new ArrayList<List<Integer>>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> list1 = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j==0||j==i){
                    list1.add(1);
                }else {
                    list1.add(list.get(i-1).get(j-1)+list.get(i-1).get(j));
                }
                list.add(list1);
            }
        }
        return list;
    }
    public class MyArraylist {

        public int[] elem;
        public int usedSize;//0
        //默认容量
        private static final int DEFAULT_SIZE = 10;

        public MyArraylist() {
            this.elem = new int[DEFAULT_SIZE];
        }

        /**
         * 打印顺序表:
         * 根据usedSize判断即可
         */
        public void display() {
            for (int i = 0; i < usedSize; i++) {
                System.out.println(elem[i]);
            }
        }

        // 新增元素,默认在数组最后新增
        public void add(int data) {
            if (isFull()){
                elem=Arrays.copyOf(elem,2*elem.length);
            }
            elem[usedSize]=data;
            usedSize++;
        }

        /**
         * 判断当前的顺序表是不是满的！
         *
         * @return true:满   false代表空
         */
        public boolean isFull() {
            if (usedSize==elem.length){
                return true;
            }
            return false;
        }


        private boolean checkPosInAdd(int pos) {

            return true;//合法
        }

        // 在 pos 位置新增元素
        public void add(int pos, int data) {

        }

        // 判定是否包含某个元素
        public boolean contains(int toFind) {
            if (isEmpty()){
                return false;
            }
            for (int i = 0; i < usedSize; i++) {
                if (elem[i]==toFind){
                    return true;
                }
            }
            return false;
        }

        // 查找某个元素对应的位置
        public int indexOf(int toFind) {
            if (isEmpty()){
                return -1;
            }
            for (int i = 0; i < usedSize; i++) {
                if (elem[i]==toFind){
                    return i;
                }
            }
            return -1;

        }

        // 获取 pos 位置的元素
        public int get(int pos) {


        }

        private boolean isEmpty() {
            if(usedSize==0){
                return true;
            }
            return false;
        }

        // 给 pos 位置的元素设为【更新为】 value
        public void set(int pos, int value) {

        }

        /**
         * 删除第一次出现的关键字key
         *
         * @param key
         */
        public void remove(int key) {

        }

        // 获取顺序表长度
        public int size() {

        }

        // 清空顺序表
        public void clear() {

        }
    }
}
